package com.base.dataStructure.heap;

import com.base.dataStructure.priorityqueue.Priority;
import com.base.leetcode.ListNode;

/**
 * @Author: hdhao
 * @Create: 2023/4/3 - 20:11
 * @Version: v1.0
 */
//小顶堆
@SuppressWarnings("all")
public class MinHeap {
    ListNode[] array;
    int size;

    public MinHeap(int capacity) {
        this.array = new ListNode[capacity];
    }
    public boolean offer(ListNode offered) {
        if(isFull()){
            return false;
        }
        int child = size++;
        int parent = (child - 1) / 2;
        while (child > 0 && offered.val < array[parent].val) {
            array[child] = array[parent];
            child = parent;
            parent = (child - 1) / 2;
        }
        array[child] = offered;
        return true;
    }
    public ListNode poll() {
        if (isEmpty()) {
            return null;
        }
        swap(0,size - 1);
        size--;
        ListNode e = array[size];
        array[size] = null;//help GC

        down(0);
        return e;
    }
    private void down(int parent) {
        int left = 2 * (parent + 1);
        int right = left + 1;
        int min = parent;//假设父元素的优先级最小
        if (left < size && array[left].val < array[min].val){
            min = left;
        }
        if (right < size && array[right].val < array[min].val){
            min = right;
        }
        if (min != parent){ //发现了有子元素比父元素大
            swap(min,parent);
            down(min);
        }
    }
    private void swap(int i, int j) {
        ListNode t = array[i];
        array[i] = array[j];
        array[j] = t;
    }
    public boolean isEmpty() {
        return size == 0;
    }
    public boolean isFull() {
        return size == array.length;
    }
}
